class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    /*
    dp[i]以s[i]结尾的最长有效括号长度，将dp数组中的最大值返回即可
    以‘（’结尾，一定构成不了有效括号，所以把‘（’对应的dp填0
    状态转移方程：dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2]
 
    */
    int longestValidParentheses(string s) {
        // write code here
        if(s.size()<2)
            return 0;
        vector<int>dp(s.size(),0);
        int maxlen=0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]==')'&&s[i-dp[i-1]-1]=='(')
                dp[i]=2+dp[i-1]+(i-dp[i-1]-2>-1?dp[i-dp[i-1]-2]:0);
            maxlen=max(dp[i],maxlen);
        }
       return maxlen;
    }
};